// 206. 反转链表
// 输入：head = [1,2,3,4,5]
// 输出：[5,4,3,2,1]
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
 var reverseList = function(head) {
    if(!head||!head.next) return head;
    let pre=null,cur=head,temp=null;
    while(cur){
        temp=cur.next;
        cur.next=pre;
        pre=cur;
        cur=temp;
    }
    return pre;
};

// 92. 反转链表 II
// 输入：head = [1,2,3,4,5], left = 2, right = 4
// 输出：[1,4,3,2,5]
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
 var reverseBetween = function(head, left, right) {
    // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
    const dummyNode=new ListNode(-1);
    dummyNode.next=head;
    let pre=dummyNode;
    // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
    // 建议写在 for 循环里，语义清晰
    for(let i=0;i<left-1;i++){
        pre=pre.next;
    }
     // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
    let rightNode=pre;
    for(let i=0;i<right-left+1;i++){
        rightNode=rightNode.next;
    }
    // 第 3 步：切断出一个子链表（截取链表）
    let leftNode=pre.next;
    let cur=rightNode.next;
    // 注意：切断链接
    pre.next=null;
    rightNode.next=null;
    // 第 4 步：同第 206 题，反转链表的子区间
    reverseLinkedList(leftNode);
     // 第 5 步：接回到原来的链表中
    pre.next=rightNode;
    leftNode.next=cur;
    return dummyNode.next; 
};
const reverseLinkedList=(head)=>{
    let pre=null;
    let cur=head;
    while(cur){
        const next=cur.next;
        cur.next=pre;
        pre=cur;
        cur=next;
    }
}

// 234. 回文链表
// 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。
// 如果是，返回 true ；否则，返回 false 。
// 输入：head = [1,2,2,1]
// 输出：true
// 思路：将链表中的值赋值到数组，然后在数组上比较是否是回文
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
 var isPalindrome = function(head) {
    const ans=[];
    let pre=head;
    while(pre){
        if(pre!=null){
            ans.push(pre.val);
            pre=pre.next;
        }
    }
    for(let i=0,j=ans.length-1;i<j;i++,j--){
        if(ans[i]!==ans[j])
            return false;
    }
    return true;
};